package leetcode.ch02_链表;

/**
 *
 * https://leetcode-cn.com/problems/reverse-linked-list/
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * @author guodd
 * @version 1.0 use jdk 1.8
 */
public class _206_反转链表 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        System.out.println(listNode);
    }

    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        ListNode newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }

    /**
     * 非递归 – 头插法
     *
     * @param head 头节点
     * @return 反转后的链表
     */
    public ListNode reverseList01(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newNode = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newNode;
            newNode = head;
            head = temp;
        }
        return newNode;
    }
}
